/*************************************************************************
	> File Name: qsort.c
	> Author: 
	> Mail: 
	> Created Time: 三  5/25 09:48:13 2016
 ************************************************************************/

#include<stdio.h>


void Qsort(int *a, int low, int high) {
    if (low >= high) {

    }
    else {
        int i, j;
        int tmp = a[low];
        i = low;
        j = high;
        int partition = 0;
        while (i < j) {
            while ( (a[i] <= tmp) && (i < j)) {
                ++i;
            }
            while (a[j] > tmp) {
                --j;
            }    //不能有等于号，比如［5，5，5］，如果有等于号，则会发生数组越界
                //不能有 i < j，比如[5,6,7,8]。若有 i < j，则 i = j = 1，程序会出现错误。或者是是[5,3,6,7]
            if (i < j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        a[low] = a[j];
        a[j] = tmp;
        partition = j;
        Qsort(a, low, partition-1);
        Qsort(a, partition+1, high);
    }
}

int main(void) {
    int a[5] = {15,6,7,8,9};
    Qsort(a, 0, 4);
    int i = 0;
    for (i = 0; i < 5; ++i) {
        printf("%d  ", a[i]);

    }
    printf("\n");
    return 0;
}
